<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
            完全背包爬楼梯
            题目描述: 爬到第n阶楼梯，每次可以爬1阶，2阶，3阶，到m阶，且可以爬了1阶，再爬1阶，再爬2阶，楼梯数就是物品，指定第几阶就是背包数，是完全背包问题
            示例 1:
                示例 1：

                输入：m = 3, n = 2（至多可以爬2层）
                输出：3
                解释：
                所有可能的组合为：
                1 + 1 + 1
                1 + 2
                2 + 1
                请注意，顺序不同的序列被视作不同的组合。
        */


        /*
            动态规划解法:
            类型：组合问题 排序
            比较：和上面的组合总和几乎是一样的，区别是这里给的不是一个数组，而是至多可以爬的楼梯数，是排序

            dp含义：dp[j] => 从0-m个阶数里面自由选择，爬到楼顶的最多的阶数
            递推公式:
                dp[j] = dp[j] + dp[j - nums[i]]
            初始化：
                dp[0]必须是1
            遍历顺序：
                先遍历背包，
                再遍历物品
            假如要爬楼梯：
                要爬4层楼梯, m = 3, nums[1, 2, 3],
                1 + 1 + 1 + 1
                1 + 2 + 1
                1 + 1 + 2
                2 + 1 + 1
                2 + 2
                1 + 3 
                3 + 1

                j = 1, dp[1] = dp[1] + dp[1 - nums[0]] = 1
                j = 2, i = 1, dp[2] = dp[2] + dp[2 - nums[0]] = 0 + 1 = 1
                j = 2, i = 2, dp[2] = dp[2] + dp[2 - nums[1]] = 1 + 1 = 2
                j = 3, i = 1, dp[3] = dp[3] + dp[3 - nums[0]] = 0 + 2 = 2
                j = 3, i = 2, dp[3] = dp[3] + dp[3 - nums[1]] = 2 + 1 = 3
                j = 3, i = 3, dp[3] = dp[3] + dp[3 - nums[2]] = 3 + 1 = 4
                j = 4, i = 1, dp[4] = dp[4] + dp[4 - nums[1]] = 0 + 4 = 4
                j = 4, i = 2, dp[4] = dp[4] + dp[4 - nums[2]] = 4 + 2 = 6
                j = 4, i = 3, dp[4] = dp[4] + dp[4 - nums[3]] = 6 + 1 = 7
        */

        /* 
            时间复杂度：O(n * m)
            空间复杂度：O(n)
        */
        var combinationSum4 = function(m, n) {
            let dp = new Array(n + 1).fill(0)
            // 第一个数必须为0
            dp[0] = 1
            // j为什么可以从0开始，因为j-nums[i]必须大于0，才能进入递推公式
            for (let j = 0; j <= n; j++) {
                // i为什么从0开始，必须每个物品都考虑在里面
                for (let i = 1; i <= m; i++) {
                    if (j < i) break
                    // 未加判断条件，得出的是NaN，会访问dp[-1]
                    if (dp[j - i] > 0) {
                        dp[j] = dp[j] + dp[j - i]
                    }
                }
            }
            return dp[n]
        };
        console.log(combinationSum4(3, 4));

        // 进阶问题：可以爬1-m个台阶应该怎么写
        // for循环，为什么必须得是背包在外面，物品在里面
    </script>
</body>

</html>